//给定一个整数矩阵，找出最长递增路径的长度。 
//
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。 
//
// 示例 1: 
//
// 输入: nums = 
//[
//  [9,9,4],
//  [6,6,8],
//  [2,1,1]
//] 
//输出: 4 
//解释: 最长递增路径为 [1, 2, 6, 9]。 
//
// 示例 2: 
//
// 输入: nums = 
//[
//  [3,4,5],
//  [3,2,6],
//  [2,2,1]
//] 
//输出: 4 
//解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
// 
// Related Topics 深度优先搜索 拓扑排序 记忆化 
// 👍 395 👎 0

package com.leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

//Java：矩阵中的最长递增路径
class P329LongestIncreasingPathInAMatrix {
    public static void main(String[] args) {
        Solution solution = new P329LongestIncreasingPathInAMatrix().new Solution();
        // TO TEST
        int[][] matrix = {{0}, {1}, {5}, {5}};
        System.out.println(solution.longestIncreasingPath(matrix));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //上下左右移动
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int rows, columns;
        int[][] longestPath;

        public int longestIncreasingPath(int[][] matrix) {
            //1.拓扑排序
//            return topological(matrix);
            //2.dfs
            //记录从每个节点出发的最长递增路径
            if (matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            rows = matrix.length;
            columns = matrix[0].length;
            longestPath = new int[rows][columns];
            int res = 0;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    res = Math.max(res, dfs(matrix, i, j));
                }
            }
            return res;
        }

        private int dfs(int[][] matrix, int row, int column) {
            if (longestPath[row][column] > 0) {
                return longestPath[row][column];
            }
            longestPath[row][column] = 1;
            for (int[] dir : dirs) {
                int newrow = row + dir[0], newcolumn = column + dir[1];
                if (newrow >= 0 && newrow < rows && newcolumn >= 0 && newcolumn < columns && matrix[newrow][newcolumn] > matrix[row][column]) {
                    longestPath[row][column] = Math.max(longestPath[row][column], dfs(matrix, newrow, newcolumn) + 1);
                }
            }
            return longestPath[row][column];
        }

        private int topological(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
            rows = matrix.length;
            columns = matrix[0].length;
            //记录每个节点的入度
            int[][] indegrees = new int[rows][columns];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < columns; j++) {
                    for (int[] dir : dirs) {
                        int newrow = i + dir[0], newcolumn = j + dir[1];
                        if (newrow >= 0 && newrow < rows && newcolumn >= 0 && newcolumn < columns && matrix[newrow][newcolumn] < matrix[i][j]) {
                            ++indegrees[i][j];
                        }
                    }
                }
            }
            //将入度为0的节点加入队列
            Queue<int[]> queue = new LinkedList<>();
            for (int i = 0; i < indegrees.length; i++) {
                for (int j = 0; j < indegrees[0].length; j++) {
                    if (indegrees[i][j] == 0) {
                        queue.offer(new int[]{i, j});
                    }
                }
            }
            int ans = 0;
            while (!queue.isEmpty()) {
                ++ans;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] cell = queue.poll();
                    int row = cell[0], column = cell[1];
                    for (int[] dir : dirs) {
                        int newrow = row + dir[0], newcolumn = column + dir[1];
                        if (newrow >= 0 && newrow < rows && newcolumn >= 0 && newcolumn < columns && matrix[newrow][newcolumn] > matrix[row][column]) {
                            --indegrees[newrow][newcolumn];
                            if (indegrees[newrow][newcolumn] == 0) {
                                queue.offer(new int[]{newrow, newcolumn});
                            }
                        }
                    }
                }
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}